1. Field of the Invention
The invention relates to cryptography and more particularly to a method and apparatus for encryption, decryption, and authentication of messages using dynamical systems.
2. Description of Related Art
Dynamical systems have been intensively studied in the academic community during the last two decades, especially as models of physical systems. A dynamical system is a set of quantities called the states of the system and a rule for mapping each state forward in time to other states.
A much-studied dynamical system is the logistic map. In a logistic map, the states of the system are real numbers x, and the rule by which the state x.sup.t at time t of the system maps to a next state s.sup.t+1 is given by x.sup.t+1 =4.lambda.x.sup.t (1-x.sup.t) where .lambda. is a real number between 0 and 1. The logistic map exhibits either simple or complex behavior depending on the value of the control parameter .lambda.. For an introduction to dynamical systems see "Determinstic Chaos" by H. G. Schuster (Physik-Verlag, 1984). For popular account of the field see "Chaos" by J. Gleick (Penguin Books, 1988).
There have been previous attempts to use dynamical systems in a cryptographic scheme.
One is described in a patent issued to M. Bianco and D. Reed, U.S. Pat. No. 5,048,086, a second is described by S. Wolfram (Proceedings of Crypto '85, pp. 429-432), a third is introduced in an article entitled "Cellular Automation Public-Key Cryptosystems" by P. Guan (Complex Systems 1, 1987), and a fourth, by J. Kari, is discussed by J-P Delahaye ("Les Automates", in Pour La Science, Nov. 1991, pp. 126-134). The first two references will be treated here as a pair since they resemble each other closely, then the second pair of reference will be considered.
Each of these first two references teaches the forward iteration of a particular dynamical system to generate a stream of pseudo-random numbers for use in encrypting. This stream is then combined with the plaintext using an XOR operation to produce a ciphertext. A receiver of the ciphertext who is in possession of the seed of the pseudo-random number generator can regenerate the stream used in encryption by again forward iterating the dynamical system. The pseudo-random numbers can be again XOR'ed with the ciphertext to recover the plaintext.
The schemes in these reference differ from each other mainly according to which dynamical system is used to generate the pseudo-random numbers. As described in U.S. Pat. No. 5,048,086, the logistic map is used as the pseudo-random number generator. The key of the system comprises the seed of the pseudo-random number generator and the parameter value of the map. In the article by Wolfram, a particular cellular automaton, known as rule 30, is used as the pseudo-random number generator. The key is the initial state of the cellular automaton.
The encryption systems taught by these two references suffer practical drawbacks including, but not limited to, the following:
The quality of the random numbers generated has not been well-established. Though Wolfram conducted extensive statistical tests on the quality of the pseudo-random numbers generated by rule 30 (see S. Wolfram, Adv. Applied Math 7, 1986) no mathematical proof has been found. The situation is worse in respect of the method taught in U.S. Pat. No. 5,048,086, since it is known that the bit sequences generated using the logistic map will not be random for most choices of the parameter in the map. The structure in the generated bit strings could be used by a code breaker to discover the key and obtain the message. PA1 The quality of encryption can vary greatly depending on which key is chosen, and it may be difficult to choose good keys. PA1 The dynamical system is used to operate on information given in the key to generate further information (a pseudo-random bit stream) which is combined only at the end of the process, so to speak externally, with the plaintext. PA1 The possible choices of dynamical systems which can be used to build cryptographic systems along these lines are limited. One must choose a dynamical system, or equivalently, parameters in a dynamical system, such that the dynamical system is strongly chaotic on almost all choices of initial condition. Proving such properties is an active area of academic research. End-users of cryptographic methods cannot be expected to conduct such research on each key they use in order to have faith in their cryptographic system. PA1 establishing a plurality of dynamical systems to be used as keys for encryption; PA1 selecting from said plurality of dynamical systems a plurality of current-key dynamical systems to be used as current keys for encryption; PA1 choosing at least one of said current-key dynamical systems, the chosen dynamical system being an irreversible dynamical system; PA1 defining a current state of at least one of the current-key dynamical systems in correspondence with at least a portion of the information to be encrypted; and PA1 applying said at least one of said current-key dynamical systems over a selected number of iteration cycles to produce from said current state a new state of said at least one of said current-key dynamical systems, said new state representing an encryption of the information. PA1 a first memory array for storing values; first data processing means connected to the first memory array, said first data processing means being operative for setting values into said first memory array in correspondence with a description for a selected dynamical system; PA1 a second memory array for storing a current state of the selected dynamical system along with other input information; and PA1 second data processing means connected to the first and second memory arrays for operating on data stored in said second memory array in accordance with the values in the first memory array to derive a new state of the selected dynamical system, respective ones of said states corresponding to the message and an encryption of the message. PA1 Resistance to code-breaking and tampering. The resistance to code-breaking and tampering of encryption with this invention is due in part to the difficulty of finding the key used for encryption from intercepted ciphertext, or by encrypting chosen plaintext. Keys are chosen randomly from a very large set. A typical implementation might for instance use radius-12 toggle rules (see below) of which there are roughly 10.sup.5.times.10.spsp.6 (1 followed by 5 million zeros). For such a system, brute-force search is clearly impossible. As demonstrated below, a one-bit error in guessing the key, the plaintext corresponding to a ciphertext or the ciphertext corresponding to a plaintext is sufficient to garble the message. PA1 Each plaintext corresponds to many ciphertexts. Part of the security of this invention is due to its property of associating many ciphertexts to each plaintext, given a fixed key. Again using the example of radius-12 rules, if encryption is carried out for 100 steps (a reasonable value) then to each plaintext there are 2.sup.2400 associated ciphertexts. This means that even if a code-breaker manages to discover a ciphertext-plaintext pair, this information will be of no use in decrypting another encipherment of the same plaintext. PA1 Implementable on computers with massively parallel architecture. Cellular automata are the simplest kind of massively parallel computer. In the preferred embodiment of this invention, the operations of both encryption and decryption are designed so that each of many different data processors can independently execute part of the computation. PA1 Implementable without floating-point arithmetic. Floating-point operations tend to be slow compared with bit operations. Further, operations calling for floating-point manipulation of numbers may be subject to round-off errors. The preferred embodiment of this invention avoids these problems by using only bit and table lookup operations. PA1 Not based on any unproven number-theoretic conjecture. The security of many of the most popular cryptographic methods is founded on one or more unproven conjectures in number theory. This invention achieves excellent security without appealing to any unproven number-theoretic conjecture. PA1 Useful in Data-Base Applications. The property possessed by this invention whereby each time a given plaintext is encrypted with a given key there results a different ciphertext is an important advantage in data-base applications. Data-base encryption poses a particularly difficult problem for encryption methods which always encrypt a given plaintext block in the same way. A data base is typically composed on a list of records, each containing a plurality of fields each labeled in a stereotyped way. If this label is always encrypted in the same way, the ciphertext can be scanned to find the label. Even if tampers cannot decrypt the label, they may be able to use their knowledge of the location of the label in the ciphertext to help insert fraudulent information. This problem will not arise in data-base encryption with this invention. PA1 Block length is not fixed. A further property of this invention useful in data-base applications is that the block length is not fixed, such as it is fixed, for instance, in the Data Encryption Standard (DES). (For information on the DES, see, for instance, E. Denning. Cryptography and Data Security, Addison-Wesley, 1982). In accordance with the present invention, blocks may be as small as one bit, or as large as the entire data base. The length of fields in a data base are seldom an exact multiple of a fixed encryption block length; hence, in a standard fixed-block-length encryption, field information must be padded in order to fit into a fixed block. This has two drawbacks--the padding could provide to a code-breaker partial information about the code and padding is wasteful of information channel capacity. These problems can be avoided by using the present invention for encryption of data bases. PA1 Embodies self-synchronizing stream cryptographic capability. A key stream is used when it is desired to encrypt different parts of a message with different keys. A particularly useful type of key stream is one automatically synchronized with the stream of ciphertext. The self-synchronizing key streams which may be generated with this invention are discussed below. PA1 Embodies error-correction capability. Error correction is needed when encrypted messages are transmitted across noisy channels. Many easily implemented approaches to error correction are possible with this invention. PA1 Embodies partial encryption/decryption capability. Essentially any prior-art encryption method may be composed with another prior-art encryption method to multiply encrypt a given message, but there is no advantage in doing so. In prior-art methods no information is extracted by the process of encryption itself. This invention however, incorporates a dynamical I/O which allows information to be extracted during decryption by one set of dynamical systems, leaving more information to be extracted by another set of dynamical systems. PA1 Each variable has only two states, labeled 0 and 1. PA1 It operates on a one-dimensional array. PA1 The cellular automaton rule used to update the value of each variable depends on the values of variable only one time step previously.
These systems, like many systems which use an XOR of the plain-text with a bit string, are vulnerable to chosen-plaintext crypt-analytic attack.
It will also be appreciated that these methods suffer major conceptual drawbacks including, but not limited to, the following:
In the second pair of systems, those taught by Guan and Kari, a reversible cellular automaton is carefully constructed so that another cellular automaton which is the original cellular automaton's inverse can be found by solving a complicated system of equations. Encryption is performed by applying the cellular automaton in the forward direction to the message. Decryption is performed by applying the inverse cellular automaton to the ciphered message. The security of the system depends on the difficulty of solving for the inverse cellular automaton. As will be brought out below in the discussion of the present invention, there are many fundamental differences between the methods taught by Guan and Kari and the present invention.